Skip to content

Latest commit

 

History

History
70 lines (55 loc) · 2.16 KB

README.md

File metadata and controls

70 lines (55 loc) · 2.16 KB

968. Binary Tree Cameras

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: root = [0,0,null,0,0] Output: 1 Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: root = [0,0,null,0,null,0,null,null,0] Output: 2 Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • Node.val == 0

Solutions (Python)

1. Solution

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightfromfunctoolsimportcacheclassSolution: @cachedefminCameraCover(self, root: Optional[TreeNode]) ->int: ifrootisNone: return0ret=self.coverBySelf(root) ifroot.leftisnotNone: ret=min(ret, self.coverBySelf(root.left) +self.minCameraCover(root.right)) ifroot.rightisnotNone: ret=min(ret, self.coverBySelf(root.right) +self.minCameraCover(root.left)) returnret@cachedefcoverBySelf(self, root: TreeNode) ->int: ret=1ifroot.leftisnotNone: ret+=self.coverByParent(root.left) ifroot.rightisnotNone: ret+=self.coverByParent(root.right) returnret@cachedefcoverByParent(self, root: TreeNode) ->int: returnmin(self.coverBySelf(root), self.minCameraCover(root.left) +self.minCameraCover(root.right))
close